package 
{
	
	
	/**
	 * A*寻路
	 * @author WLDragon
	 */
	public class AStar
	{
		/**
		 * 构造函数
		 * @param	$map 地图数据
		 */
		public function AStar()
		{
		}
		
		public function setMap($map:Array):void
		{
			mOpenList = new Vector.<Node>;
			mMap = [];
			
			mMapH = $map.length;
			mMapW = $map[0].length;
			
			for (var i:int = 0; i < mMapH; i++)
			{
				if (mMap[i] == undefined)
				{
					mMap[i] = [];
				}
				
				for (var j:int = 0; j < mMapW; j++)
				{
					//是否为障碍
					var b:Boolean;
					if ($map[i][j] == 1 )
					{
						b = false;
					}
					else
					{
						b = true;
					}
					
					mMap[i][j] = new Node(j, i, b);
				}
			}
		}
		
		/**
		 * 该点是否可达
		 * @param	$x
		 * @param	$y
		 * @return
		 */
		public function canReach($x:int, $y:int):Boolean
		{
			if ($x >= 0 && $x < mMapW && $y >= 0 && $y < mMapH)
			{
				if (mMap[$y][$x].isBlock)
				{
					return false;
				}
				return true;
			}
			return false;
		}
		
		
		/**
		 * 寻路(返回的路径是从目的节点往开始节点排列的，应用pop方法提取)
		 * 在使用find方法之前请先使用testWalk测试该点是否可走
		 * @param	$start 开始点
		 * @param	$end 目的点
		 * @param   $type 寻路类型（8方向或4方向）
		 * @return
		 */
		public function find($start:Array, $end:Array ,$type:int):Array
		{
			//重置"open list"和节点的开启关闭状态
			reset();

			//添加开始节点到"open list"
			mStartNode = mMap[$start[1]][$start[0]];
			mEndNode = mMap[$end[1]][$end[0]];
			addToOpenList(mStartNode, 0, 0, null);
			
			while (mOpenList.length > 0)
			{
				//把F值最小的节点从"open list"中拿出作为当前节点,并把它设为关闭状态
				var curNode:Node = mOpenList.splice(getLeast(), 1)[0];
				if (curNode == mEndNode)
				{
					//返回搜索到的路径
					return getPath();
				}
				curNode.isClosed = true;
				
				//获取当前节点的附近可走节点
				var around:Vector.<Node>;
				if ($type == 8)
				{
					around = getAround8(curNode);
				}
				else
				{
					around = getAround4(curNode);
				}
				
				for each (var n:Node in around)
				{
					//计算G\H值
					var g:int = curNode.G + ((n.mX == curNode.mX || n.mY == curNode.mY) ? COST_STRAIGHT : COST_DIAGONAL);
					//曼哈顿式评估
					var h:int = (Math.abs(n.mX - mEndNode.mX) + Math.abs(n.mY - mEndNode.mY)) * COST_STRAIGHT;
					//欧几里式
					//var h:int = Math.sqrt(Math.pow(Math.abs(n.mX - mEndNode.mX),2) + Math.pow(Math.abs(n.mY - mEndNode.mY),2));

					//判断是否在"open list"
					if (n.isOpen == true)
					{
						//检查路径是否较优
						if (g < n.G)
						{
							n.G = g;
							n.F = g + h;
							n.mParent = curNode;
						}
					}
					else
					{
						//添加到"open list"
						addToOpenList(n, g, h, curNode);
					}
				}
			}
			
			return null;
		}
		
		/**
		 * 测试该节点是否可走
		 * @param	$x x坐标
		 * @param	$y y坐标
		 * @return 是否可走
		 */
		private function testWalk($x:int, $y:int):Boolean
		{
			if ($x >= 0 && $x < mMapW && $y >= 0 && $y < mMapH)
			{
				if (mMap[$y][$x].isBlock == false && mMap[$y][$x].isClosed == false)
				{
					return true;
				}
			}
			return false;
		}
		
		/**
		 * 重置"open list"和各节点的状态
		 */
		private function reset():void
		{
			mOpenList.length = 0;
			
			for each (var arr:Array in mMap)
			{
				for each (var n:Node in arr)
				{
					n.reset();
				}
			}
		}
		
		/**
		 * 获取已找到的路径
		 * @return 路径（[[x1,y1],[x2,y2]......）
		 */
		private function getPath():Array
		{
			var path:Array = [];
			var n:Node = mEndNode;
			while (n != mStartNode)
			{
				path.push([n.mX, n.mY]);
				n = n.mParent;
			}
			path.push([mStartNode.mX, mStartNode.mY]);
			return path;
		}
		
		/**
		 * 获取"open list"中F值最小的节点
		 * @return 节点的序号
		 */
		private function getLeast():int
		{
			var least:int = mOpenList[0].F;
			var index:int = 0;
			for (var i:int = 1; i < mOpenList.length; i++)
			{
				if (least > mOpenList[i].F)
				{
					least = mOpenList[i].F;
					index = i;
				}
			}
			
			return index;
		}
		
		/**
		 * 把节点添加到"open list"
		 * @param	$x
		 * @param	$y
		 * @param	$G
		 * @param	$H
		 * @param	$parent
		 */
		private function addToOpenList($n:Node, $G:int, $H:int, $parent:Node):void
		{
			$n.G = $G;
			$n.F = $G + $H;
			$n.mParent = $parent;
			$n.isOpen = true;
			mOpenList.push($n);
		}
		
		/**
		 * 8方向获取当前节点附近的可走节点
		 * @param	$n 当前节点
		 * @return
		 */
		private function getAround8($n:Node):Vector.<Node>
		{
			var vec:Vector.<Node> = new Vector.<Node>;
			var tx:int;
			var ty:int;
			//先判断上-0\下-1\左-2\右-3四个方向是否可走
			var dir:Array = [{x: 0, y: -1}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 1, y: 0}];
			var able:Vector.<Boolean> = new Vector.<Boolean>;
			for (var i:int = 0; i < 4; i++)
			{
				tx = $n.mX + dir[i].x;
				ty = $n.mY + dir[i].y;
				able[i] = testWalk(tx, ty);
				if (able[i])
				{
					vec.push(mMap[ty][tx]);
				}
			}
			//左上
			if (able[2] || able[0])
			{
				tx = $n.mX - 1;
				ty = $n.mY - 1;
				if (testWalk(tx, ty))
				{
					vec.push(mMap[ty][tx]);
				}
			}
			//右上
			if (able[3] || able[0])
			{
				tx = $n.mX + 1;
				ty = $n.mY - 1;
				if (testWalk(tx, ty))
				{
					vec.push(mMap[ty][tx]);
				}
			}
			//左下
			if (able[2] || able[1])
			{
				tx = $n.mX - 1;
				ty = $n.mY + 1;
				if (testWalk(tx, ty))
				{
					vec.push(mMap[ty][tx]);
				}
			}
			//右下
			if (able[3] || able[1])
			{
				tx = $n.mX + 1;
				ty = $n.mY + 1;
				if (testWalk(tx, ty))
				{
					vec.push(mMap[ty][tx]);
				}
			}
			
			return vec;
		}
		
		/**
		 * 4方向获取当前节点附近的可走节点
		 * @param	$n 当前节点
		 * @return
		 */
		private function getAround4($n:Node):Vector.<Node>
		{
			var vec:Vector.<Node> = new Vector.<Node>();
			var tx:int;
			var ty:int;
			//先判断上-0\下-1\左-2\右-3四个方向是否可走
			var dir:Array = [{x: 0, y: -1}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 1, y: 0}];
			var able:Vector.<Boolean> = new Vector.<Boolean>();
			for (var i:int = 0; i < 4; i++)
			{
				tx = $n.mX + dir[i].x;
				ty = $n.mY + dir[i].y;
				able[i] = testWalk(tx, ty);
				if (able[i])
				{
					vec.push(mMap[ty][tx]);
				}
			}
			
			return vec;
		}

		/**open list*/
		private var mOpenList:Vector.<Node>;
		/**地图数据(节点集)*/
		private var mMap:Array;
		/**地图横向节点数*/
		private var mMapW:int;
		/**地图纵向节点数*/
		private var mMapH:int;
		/**开始节点*/
		private var mStartNode:Node;
		/**目标节点*/
		private var mEndNode:Node;
		
		/**横或竖向移动一格的路径评分*/
		private const COST_STRAIGHT:int = 10;
		/**斜向移动一格的路径评分*/
		private const COST_DIAGONAL:int = 14;

	}
}

/**
 * 节点
 */
class Node
{
	/**
	 * 节点构造方法
	 * @param	$x x坐标
	 * @param	$y y坐标
	 * @param	$b 是否为障碍
	 */
	public function Node($x:int, $y:int, $b:Boolean)
	{
		mX = $x;
		mY = $y;
		isBlock = $b;
	}
	
	/**
	 * 重置节点属性值
	 */
	public function reset():void
	{
		F = 0;
		G = 0;
		isOpen = false;
		isClosed = false;
		mParent = null;
	}
	
	public var F:int;
	public var G:int;
	public var mParent:Node;
	public var isOpen:Boolean;
	public var isClosed:Boolean;
	public var isBlock:Boolean;
	public var mX:int;
	public var mY:int;
}